/*
 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
 *
 *  This file is licensed to You under the Eclipse Public License (EPL);
 *  You may not use this file except in compliance with the License. You
 *  may obtain a copy of the License at
 *
 *      http://www.opensource.org/licenses/eclipse-1.0.php
 *
 *  See the COPYRIGHT.txt file distributed with this work for information
 *  regarding copyright ownership.
 */
package org.mmtk.plan.compressor;


import org.mmtk.policy.Space;

import org.mmtk.policy.compressor.MarkCopySpace;
import org.mmtk.plan.*;
import org.mmtk.utility.DoublyLinkedList;
import org.mmtk.utility.Log;
import org.mmtk.utility.heap.VMRequest;
import org.mmtk.utility.sanitychecker.SanityChecker;

import org.vmmagic.pragma.*;
import org.vmmagic.unboxed.*;

/**
 * This class implements a simple semi-space collector. See the Jones
 * & Lins GC book, section 2.2 for an overview of the basic
 * algorithm. This implementation also includes a large object space
 * (LOS), and an uncollected "immortal" space.<p>
 *
 * All plans make a clear distinction between <i>global</i> and
 * <i>thread-local</i> activities.  Global activities must be
 * synchronized, whereas no synchronization is required for
 * thread-local activities.  Instances of Plan map 1:1 to "kernel
 * threads" (aka CPUs).  Thus instance
 * methods allow fast, unsychronized access to Plan utilities such as
 * allocation and collection.  Each instance rests on static resources
 * (such as memory and virtual memory resources) which are "global"
 * and therefore "static" members of Plan.  This mapping of threads to
 * instances is crucial to understanding the correctness and
 * performance proprties of this plan.
 */
@Uninterruptible
public class Compressor extends StopTheWorld implements org.mmtk.utility.Constants {

  /****************************************************************************
   *
   * Class variables
   */

  /** True if allocating into the "higher" semispace */
  public static boolean hi = false;

  /** One of the two semi spaces that alternate roles at each collection */
  public static final MarkCopySpace markCopySpace0 = new MarkCopySpace("mark-copy-0", DEFAULT_POLL_FREQUENCY, false, VMRequest.create());
  public static final int MC0 = markCopySpace0.getDescriptor();

  /** One of the two semi spaces that alternate roles at each collection */
  public static final MarkCopySpace markCopySpace1 = new MarkCopySpace("mark-copy-1", DEFAULT_POLL_FREQUENCY, true, VMRequest.create());
  public static final int MC1 = markCopySpace1.getDescriptor();
  
  public final DoublyLinkedList calculateHeads = new DoublyLinkedList(LOG_BYTES_IN_PAGE, true);
  public final DoublyLinkedList preallocCopyHeads = new DoublyLinkedList(LOG_BYTES_IN_PAGE, true);
  public final DoublyLinkedList allocationHeads = new DoublyLinkedList(LOG_BYTES_IN_PAGE, true);
  
  public static final short PREALLOC_COPY = Phase.createSimple("prealloc-and-copy");
  public static final short CALC_METADATA = Phase.createSimple("calculate-metadata");

  public static final short PREPARE_FORWARD = Phase.createSimple("prepare-foreward");
  public static final short FORWARD_CLOSURE = Phase.createSimple("forward-closure");
  public static final short RELEASE_FORWARD = Phase.createSimple("release-foreward");
  public static final short PUSH_MUTATOR_HEADS = Phase.createSimple("push-mutator-heads");
  
  public final Trace markTrace;
  public final Trace forwardTrace;

  
  
  //CHECKSTYLE:OFF
  
  /**
   * This is the phase that is executed to perform a collection.
   */
  public short compressorCollection = Phase.createComplex("collection", null,
      Phase.scheduleComplex(initPhase),
      Phase.scheduleComplex(rootClosurePhase),
      Phase.scheduleComplex(refTypeClosurePhase),
      
      Phase.scheduleMutator  (PUSH_MUTATOR_HEADS),
      
      Phase.scheduleGlobal   (PREPARE_FORWARD),
      Phase.scheduleCollector(PREPARE_FORWARD),
      Phase.scheduleMutator  (PREPARE),
      Phase.scheduleCollector(STACK_ROOTS),
      Phase.scheduleCollector(ROOTS),
      Phase.scheduleGlobal   (ROOTS),
      Phase.scheduleComplex  (forwardPhase),
      
      Phase.scheduleCollector(CALC_METADATA),
      Phase.scheduleCollector(PREALLOC_COPY),
      
      Phase.scheduleCollector(FORWARD_CLOSURE),
      
      Phase.scheduleComplex(completeClosurePhase),
      
      Phase.scheduleCollector(RELEASE_FORWARD),
      Phase.scheduleGlobal   (RELEASE_FORWARD),
      
      Phase.scheduleComplex(finishPhase));

  // CHECKSTYLE:ON
  
  public static boolean ready = false;

  

  
  /****************************************************************************
   *
   * Initialization
   */

  public Compressor() {
    markTrace = new Trace(metaDataSpace);
    forwardTrace = new Trace(metaDataSpace);
    collection = compressorCollection;
  }
  
  /**
   * Class variables
   */
  public static final int ALLOC_MC = Plan.ALLOC_DEFAULT;
  public static final int SCAN_MARK = 0;
  public static final int SCAN_FORWARD = 1;
  
  public static final boolean VERBOSE = false;
  
  /**
   * @return The to space for the current collection.
   */
  @Inline
  public static MarkCopySpace toSpace() {
    return hi ? markCopySpace1 : markCopySpace0;
  }

  /**
   * @return The from space for the current collection.
   */
  @Inline
  public static MarkCopySpace fromSpace() {
    return hi ? markCopySpace0 : markCopySpace1;
  }


  /****************************************************************************
   *
   * Collection
   */

  /**
   * Perform a (global) collection phase.
   *
   * @param phaseId Collection phase
   */
  @Inline
  public void collectionPhase(short phaseId) {
    if (phaseId == Compressor.PREPARE) {
      hi = !hi; // flip the semi-spaces
      
      // prepare each of the collected regions
      markCopySpace0.prepare(hi);
      markCopySpace1.prepare(!hi);
      markTrace.prepare();
      
      super.collectionPhase(phaseId);
      return;
    }
    if (phaseId == CLOSURE) {
      markTrace.prepare();
      return;
    }
    
    if (phaseId == Compressor.RELEASE) {
      markTrace.release();
      
      // Release the collected region
      fromSpace().release();

      super.collectionPhase(phaseId);
      return;
    }
    
    if (phaseId == Compressor.COMPLETE) {
      super.collectionPhase(phaseId);
      ready = true;
    }

    if (phaseId == PREPARE_FORWARD) {
      super.collectionPhase(PREPARE);
      forwardTrace.prepare();
      return;
    }
    if (phaseId == RELEASE_FORWARD) {
      forwardTrace.release();
      super.collectionPhase(RELEASE);
      return;
    }
    
    super.collectionPhase(phaseId);
  }

  
  /****************************************************************************
   *
   * Accounting
   */

  /**
   * Return the number of pages reserved for copying.
   *
   * @return The number of pages reserved given the pending
   * allocation, including space reserved for copying.
   */
  public final int getCollectionReserve() {
    // we must account for the number of pages required for copying,
    // which equals the number of semi-space pages reserved
    return toSpace().reservedPages() + super.getCollectionReserve();
  }

  /**
   * Return the number of pages reserved for use given the pending
   * allocation.  This is <i>exclusive of</i> space reserved for
   * copying.
   *
   * @return The number of pages reserved given the pending
   * allocation, excluding space reserved for copying.
   */
  public int getPagesUsed() {
    return super.getPagesUsed() + toSpace().reservedPages();
  }

  /**
   * Return the number of pages available for allocation, <i>assuming
   * all future allocation is to the semi-space</i>.
   *
   * @return The number of pages available for allocation, <i>assuming
   * all future allocation is to the semi-space</i>.
   */
  public final int getPagesAvail() {
    return(super.getPagesAvail()) >> 1;
  }

  /**
   * Calculate the number of pages a collection is required to free to satisfy
   * outstanding allocation requests.
   *
   * @return the number of pages a collection is required to free to satisfy
   * outstanding allocation requests.
   */
  public int getPagesRequired() {
    return super.getPagesRequired() + (toSpace().requiredPages() << 1);
  }

  /**
   * @see org.mmtk.plan.Plan#willNeverMove
   *
   * @param object Object in question
   * @return True if the object will never move
   */
  @Override
  public boolean willNeverMove(ObjectReference object) {
    if (Space.isInSpace(MC0, object) || Space.isInSpace(MC1, object))
      return false;
    return super.willNeverMove(object);
  }

  /**
   * Register specialized methods.
   */
  @Interruptible
  protected void registerSpecializedMethods() {
    TransitiveClosure.registerSpecializedScan(SCAN_MARK, CompressorTraceLocal.class);
    TransitiveClosure.registerSpecializedScan(SCAN_FORWARD, CompressorForwardTraceLocal.class);
    super.registerSpecializedMethods();
  }
}
